package 开始的剑指offer8月.数学;
// https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=188&&tqId=38622&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
public class 跳台阶0816 {
    public class Solution {
        public int JumpFloor(int n) {
            if (n == 1) return 1;
            if (n == 2) return 2;
            return JumpFloor(n - 1) + JumpFloor(n - 2);
        }
    }

    public class Solution1 {
        public int JumpFloor(int target) {
            // f[1] = 1, f[0] = 1 (f[0]是为了简便作答自己添加的)
            int a = 1, b = 1;
            for (int i = 2; i <= target; i++) {
                // 求f[i] = f[i - 1] + f[i - 2]
                a = a + b; // 这里求得的 f[i] 可以用于下次循环求 f[i+1]
                // f[i - 1] = f[i] - f[i - 2]
                b = a - b; // 这里求得的 f[i-1] 可以用于下次循环求 f[i+1]
            }
            return a;
        }
    }

    public class Solution2 {
        public int JumpFloor(int target) {
            if (target <= 1) {
                return 1;
            }
            // a 表示第 f[i-2] 项，b 表示第 f[i-1] 项
            int a = 1, b = 1, c = 0;
            for (int i = 2; i <= target; i++) {
                c = a + b; // f[i] = f[i - 1] + f[i - 2];
                // 为下一次循环求 f[i + 1] 做准备
                a = b; // f[i - 2] = f[i - 1]
                b = c; // f[i - 1] = f[i]
            }
            return c;
        }
    }
}
